iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 10

[Day10]程式菜鳥自學C++資料結構演算法 – 堆 疊應用:數制轉換&括號匹配&漢諾塔

  • 分享至 

  • xImage
  •  

前言:今天要來實作數制轉換、括號匹配和河內塔,這三個範例都是非常知名的堆疊應用,甚至會是程式競賽的考題,所以今天就來帶大家看看這些題目。

數制轉換:

一樣新增一個新的專案,這邊注意一點,因為等等的練習同樣需要用到上一篇寫好的Stack,所以可以先把程式碼複製下來(不包含main程式),並新增一個標頭檔,這樣只要呼叫出來就可以了,不用在重寫一次。
https://ithelp.ithome.com.tw/upload/images/20210924/20140187bVwjlHRJJg.png
https://ithelp.ithome.com.tw/upload/images/20210924/20140187aD1VVDJBbi.png
之後就開始實作了。

先解釋std::cin >>s的意思,這個程式的意思是,先建立一個變數,輸入一個數字後換行,之後"cin"就是從鍵盤打數字,這個數字會儲存到變數"s"裡面
https://ithelp.ithome.com.tw/upload/images/20210924/20140187xlCtqHarq2.png

此範例用二進位制換算,更改d的值就能轉換成不同進位。
https://ithelp.ithome.com.tw/upload/images/20210924/20140187o0VEExdyJy.png
這樣就完成了,是不是很簡單,那我們繼續下一題。

括號匹配:

直接在這個專案新增項目就好,不用創建新的專案,但這邊要注意一個專案不能有兩個main程式,所以必須在之前實作的main程式用#if 0 和 #end if包起來。
https://ithelp.ithome.com.tw/upload/images/20210924/201401873MGpUgy67v.png

程式碼範例
https://ithelp.ithome.com.tw/upload/images/20210924/20140187W5fXOacThO.png
https://ithelp.ithome.com.tw/upload/images/20210924/201401870KAT0iW5cj.png

實作結果
https://ithelp.ithome.com.tw/upload/images/20210924/20140187ocJmmBYsrj.png
這樣就成功了,括號匹配雖然看似簡單但是其實是非常重要的,還是不能輕忽!

河內塔問題:

先來解釋河內塔的遊戲規則。
有三根桿子A,B,C。A桿上有數個穿孔圓盤,盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿;
每次只能移動一個圓盤且大盤不能疊在小盤上面。
提示:可將圓盤臨時置於B桿,也可將從A桿移出的圓盤重新移回A桿,但都必須遵循上述兩條規則。
試問要如何移?
https://ithelp.ithome.com.tw/upload/images/20210924/20140187u2SBRafeyx.png
圖片來源:https://sites.google.com/a/g2.nctu.edu.tw/unimath/_/rsrc/1512212597474/manuscript/hanoi/%E5%9C%96%E7%89%871.png?height=208&width=400

這就是河內塔的遊戲規則,接下來就用實作一一解答。
https://ithelp.ithome.com.tw/upload/images/20210924/20140187EYL143jtVC.png
程式碼基本上就是這樣運行(用寫的太複雜,還是用畫的好了)
https://ithelp.ithome.com.tw/upload/images/20210924/201401870cU6jx1KJu.png
https://ithelp.ithome.com.tw/upload/images/20210924/201401873oeszD3fMD.png
https://ithelp.ithome.com.tw/upload/images/20210924/20140187wmbSdFDU7V.png

結果就如下圖
https://ithelp.ithome.com.tw/upload/images/20210924/20140187ghScJZ8xrA.png
三個盤子,共要移動七次,也可以加上移動次數讓程式碼更完整。

本日小結:今天一次就講了三個實作,雖然很累但是也感覺非常充實,三道題目的程式碼都不長,不過括號匹配和河內塔的想法比較複雜,不是三五分鐘就可以搞懂的。這些題目所運用到的技術都有可能在未來使用到,不要認為這些程式碼只能用在對應的題目上,能融會貫通才是真正的學會喔(∩_∩)
明天也將要進入新的單元,大家加油!!!

堆疊標頭檔

#pragma once
template<typename T>
class SqlStack {
	T* data, * top_; //建立指針變量T指向元素,及top_指向堆疊的位置
	int capacity;

public:
	SqlStack(int cap = 3) {
		data = new T[cap];
		if (!data) { top_ = 0; capacity = 0; return; } //創建失敗的情況
		top_ = data; capacity = cap; //創建成功的條件
	}
	T& top() { //編寫top()檢查堆疊是否為空的,並返回T類型的引用變量
		if (top_ == data) throw "堆疊為空";
		return *(top_ - 1);
	}
	bool push(T e) { //編寫push()函式,且容量也會隨資料的增加變多
		if (top_ - data == capacity) {
			T* p = new T[2 * capacity];
			if (!p) return false;
			for (int i = 0; i < capacity; i++)
				p[i] = data[i];
			delete[] data; data = p;
			top_ = data + capacity;
			capacity = 2 * capacity;
		}
		*top_ = e; top_++; return true;
	}
	bool pop() { //編寫pop()函示,需先判對堆疊是否為空
		if (top_ == data) return false;
		top_--; return true;
	}
	bool empty() { //檢查堆疊是不是空的,與top()相同概念
		return top_ == data;
	}
	void clear() { //清除堆疊所有元素
		top_ == data;
	}
};

數制轉換

#include "SqlStack.h";
#include <iostream>;
using namespace std;

int main() {
	int n,d; //n為輸入的數字,d為要轉換的進制
	std::cin >> n;
	std::cin >> d;
	SqlStack<int> s;
	while (n) {
		s.push(n % d);
		n = n / d;
	}
	while (!s.empty()) {
		auto e = s.top();
		std::cout << e;
		s.pop();
	}
}

括號匹配

#include <iostream>
#include <string>
#include "SqlStack.h"
using std::string;
bool isLeft(char ch) { //判斷是否為左括弧
	return  ch == '(' || ch == '[' || ch == '{';
}
bool isRight(char ch) { //判斷是否為右括弧
	return  ch == ')' || ch == ']' || ch == '}';
}
bool isMatch(const char c1,const char c2) { //判斷是否匹配,const表示不會修改到
	if (c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}')
		return true;
	return false;
}
bool is_match(string s) {
	SqlStack<char> stack;
	for (int i = 0; i <= s.size(); i++) {
		if (isLeft(s[i])) { //遇到左括弧則放入堆疊內
			stack.push(s[i]);
		}
		else if (isRight(s[i])) { //遇到右括弧則放到堆疊外
			if (stack.empty()) return false;
			char c = stack.top();
			if (!isMatch(c, s[i])) return false;
			stack.pop();
		}
	}
	if (stack.empty()) { //如果最後堆疊為空,表示括號匹配成功
		return true;
	return false;
	}
}

int main() {
	string s;
	std::cin >> s; //輸入s字串
	if(is_match(s))
		std::cout << s << "匹配成功";
	else 
		std::cout << s << "匹配失敗";
	return 0;
}

漢諾塔

#include<iostream>
void move(int x, char a, char b) {
	std::cout << x << "從" << a << "移到" << b << "\n";
}

void hanoi(int n, char x, char y, char z) { //n個盤字和xyz三根柱子,x為起點,z為終點,y為輔助
	if (n == 1) move(n, x, z); //只有一個盤子,從x移到z即可
	else {
		hanoi(n - 1, x, z, y); 
		move(n, x, z); 
		hanoi(n - 1, y, x, z); 
	}
}

int main() {
	hanoi(3, 'A', 'B', 'C');
}

上一篇
[Day09]程式菜鳥自學C++資料結構演算法 – 堆疊Stack介紹與建立
下一篇
[Day11]程式菜鳥自學C++資料結構演算法 – 佇 列Queue
系列文
程式菜鳥自學C++資料結構演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言